package com.sam.sort;

import java.util.Arrays;

/**
 * 排列逆序数：
 * 数组a 存在jk,j < k && a[j] > a[k],则(a[j],a[k])是a的一个逆序
 * <p>
 * 给a，就逆序数如{2643}，逆序数有(6,4),(6,3),(4,3)
 * <p>
 * 1.枚举 O(n^2)
 * 2.分治 O(nlogn)
 *  将数组分为一半求左半+右半的逆序数+左一右一情况下的逆译成数
 *  归并排序+逆序数计算
 * Created by samwang on 2017/12/17.
 */
public class ArrayInverse {
    public static void main(String[] args) {
        int[] a = {2, 6, 4, 3};
        int result = mergeSortAndCount(a, 0, a.length - 1, new int[a.length]);
        System.out.println(Arrays.toString(a));
        System.out.println( result);
    }

    public static int mergeSortAndCount(int[] a, int s, int e,int[] temp) {
        if (s < e) {
            int mid = (s + e) / 2;
            int l = mergeSortAndCount(a, s, mid, temp);
            int r = mergeSortAndCount(a, mid + 1, e, temp);
            int lr = mergeArrayAndCount(a, s, mid, e, temp);
            return l + r + lr;
        }
        return 0;
    }

    public static int mergeArrayAndCount(int[] a, int s, int m, int e, int[] temp) {
        int i = s;
        int j = m + 1;
        int k = s;//for temp
        int count = 0;
        // 5 4 1 | 6 2 3


        while (i <= m && j <= e) {
            if (a[i] <= a[j]) {
                temp[k] = a[j];
                j++;
            } else {
                temp[k] = a[i];
                count += e - j + 1;
                i++;
            }
            k++;
        }
        while (i <= m) {
            temp[k] = a[i];
            k++;
            i++;
        }
        while (j <= e) {
            temp[k] = a[j];
            k++;
            j++;
        }

        for (int l = s; l <= e; l++) {
            a[l] = temp[l];
        }


        return count;
    }
}
